#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

// 稠密图 - 邻接矩阵 Adjacency Matrix
template <typename Weight>
class DenseGraph{
	private:
		int n, m;		// 图的点数和边数
		bool directed;  // 是否有向
		vector<vector<Edge<Weight> *>> g; // 二维矩阵
	
	public:
		// 顶点数 n
		DenseGraph(int n, bool directed){
			this->n = n;
			this->m = 0;
			this->directed = directed;
			// 创建 n*n 名称为g矩阵, 
			for(int i = 0; i < n; ++i){
				// 存放 Edge<Weight> 类型指针
				g.push_back(vector<Edge<Weight> *>(n, NULL));
			}
		}

		// 没有new 任何空间
		~DenseGraph(){
			for(int i = 0; i < n; ++i){
				for(int j = 0; j < n; ++j){
					if(g[i][j] != NULL){
						delete g[i][j];
					}
				}
			}
		}

		int V(){ return n;}		// 图的节点数
		int E(){ return m;}     // 图的边数

		/**
		 * 添加边, 在 v 和 w 之间
		 * v,w 顶点相应的索引
		 * 发现 vw 已经有边,直接return,去掉了平行变问题
		 * 
		 * */
		void addEdge(int v, int w, Weight weight){
			assert(v >= 0 && v < n);
			assert(w >= 0 && w < n);

			// 如果已经有边,覆盖掉原来的边
			if(hasEdge(v, w)){	
				delete g[v][w];
				if(!directed)
					delete g[w][v];
				m--;
			}
			// 连通 v w 两点，添加一个边,加上权值
			g[v][w] = new Edge<Weight>(v, w, weight);	
			if(!directed){		// 判断是否为有向图
				g[w][v] = new Edge<Weight>(w, v, weight); // 无向图 是双向的有向图
			}
			m++;				 // 边数增加
		}

		// 判断两个边是否连通
		bool hasEdge(int v, int w){
			assert(v >= 0 && v < n);
			assert(w >= 0 && w < n);
			return g[v][w] != NULL;
		}

		void show(){
			for(int i = 0;i < n; ++i){
				for(int j = 0; j < n; ++j){
					if(g[i][j])
						cout << g[i][j]->wt() << "\t";
					else
						cout << "NULL \t";
				}
				cout << endl;
			}
		}


		class adjIterator{
		private:
			DenseGraph &G;			// 存储图的引用
			int v;					// 存储图迭代的节点
			int index;				// 当前迭代到哪里
		public:
			/**
			 * 传入迭代图的引用 &graph
			 * 迭代图中那个节点
			 * 使用构造列表方式初始化
			 **/
			adjIterator(DenseGraph &graph, int v): G(graph){
				this->v = v;
				this->index = -1;
			}

			// 遍历v所在一行中所有元素,  找到第一个为true的元素
			Edge<Weight>* begin(){
				index = -1;
				return next();
			}

			// 当前迭代的元素找第一个为true元素
			Edge<Weight>* next(){
				for(index += 1; index < G.V(); index++){
					if(G.g[v][index]){
						return G.g[v][index];
					}
				}
				return NULL;
			}

			// 迭代是否终止
			bool end(){
				return index >= G.V();  // 已经越界
			}
		};
};
